import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
//两个队列模拟栈
class MyStackUsQueue {
    public Queue<Integer> queue1;
    public Queue<Integer> queue2;

    public MyStackUsQueue() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    //入栈
    public void push(int x) {
        if (empty()) {
            queue1.offer(x);
            return;
        }
        if (!queue1.isEmpty()) {
            queue1.offer(x);
        }else {
            queue2.offer(x);
        }
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (!queue1.isEmpty()) {
            int size = queue1.size();
            for (int i = 0; i < size-1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue1.poll();
        }else {
            int size = queue2.size();
            for (int i = 0; i < size-1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }


    //获取栈顶元素
    public int top() {
        if (empty()) {
            return -1;
        }
        if (!queue1.isEmpty()) {
            int size = queue1.size();
            int ret = -1;
            for (int i = 0; i < size; i++) {
                ret = queue1.poll();
                queue2.offer(ret);
            }
            return ret;
        }
//        return ret;
        return -1;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

//两个栈模拟队列
class MyQueueUsStack {
    public ArrayDeque<Integer> s1;
    public ArrayDeque<Integer> s2;
    public MyQueueUsStack() {
        s1 = new ArrayDeque<>();
        s2 = new ArrayDeque<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }         
        return s2.pop();
    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

//循环队列
class MyCircularQueue {
    public int[] elem;
    public int first;
    public int last;

    public MyCircularQueue(int k) {
        elem = new int[k];
    }

    public  boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[last] = value;
        last = (last+1) % elem.length;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        first = (first+1) % elem.length;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[first];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        int index = (last == 0) ? elem.length-1 : last-1;
        return elem[index];
    }


    public boolean isFull() {
        return (last+1) % elem.length == first;
    }

    public boolean isEmpty() {
        return first == last;
    }
}

//最小栈
class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }


    public void push(int val) {
        stack.push(val);
        if (minStack.empty()) {
            minStack.push(val);
        }else {
            Integer peekVal = minStack.peek();
            if (val <= peekVal) {
                minStack.push(val);
            }
        }
    }


    public void pop() {
        if (stack.empty()) {
            return;
        }
        int popVal = stack.pop();
        if (popVal == minStack.peek()) {
            minStack.pop();
        }
    }

   

    public int top() {
        if (stack.empty()) {
            return -1;
        }
        return stack.peek();
    }

    //获取栈中的最小值
    public int getMin() {
        if (minStack.empty()) {
            return -1;
        }
        return minStack.peek();
    }
}


public class Text {
    public static void main(String[] args) {

    }


    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            }else {
                if (stack.empty()) {
                    return false;
                }else {
                    char chL = stack.peek();
                    if (chL == '(' && ch == ')' || chL == '[' && ch == ']' || chL == '{' && ch == '}') {
                        stack.pop();
                    }else {
                        return false;
                    }
                }

            }
        }
        return stack.empty();
    }
}

